#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2019 crane <crane@gosun>
#
# Distributed under terms of the MIT license.

"""
https://www.lintcode.com/problem/sort-integers-ii/description
"""

class Solution:
    """
    @param A: an integer array
    @return: nothing
    """
    def sortIntegers2(self, A):
        self.len = len(A)
        # base  = list(A)             #
        extra = list(A)

        l = self.mergesort_rec(A, extra, 0, self.len)
        return A
        # print(base)

    def bubble_sort(self, base, b_idx, e_idx):
        for i in range(b_idx, e_idx):
            for j in range(e_idx-1, i, -1):
                if base[j-1] >= base[j]:
                    base[j-1], base[j] = base[j], base[j-1]
        # print('bubble ', base)
        # return base

    def mergesort_rec(self, base, extra, b_idx, e_idx):
        # [b, e) 开闭区间
        if e_idx - b_idx < 9:
            self.bubble_sort(base, b_idx, e_idx)
            return

        # if e_idx - b_idx == 1:
        #     return

        mid_idx = (b_idx + e_idx) // 2
        self.mergesort_rec(extra, base, b_idx, mid_idx)
        self.mergesort_rec(extra, base, mid_idx, e_idx)
        self.merge(extra, base, b_idx, mid_idx, e_idx)

    def merge(self, src, dst, b_idx, mid_idx, e_idx):
        left_idx = b_idx
        right_idx = mid_idx
        extra_idx = b_idx

        while left_idx < mid_idx and right_idx < e_idx:
            if src[left_idx] <= src[right_idx]:
                hit = left_idx
                left_idx += 1
            else:
                hit = right_idx
                right_idx += 1
            dst[extra_idx] = src[hit]
            extra_idx += 1

        if left_idx == mid_idx:
            dst[extra_idx:e_idx] = src[right_idx:e_idx]
        else:
            dst[extra_idx:e_idx] = src[left_idx:mid_idx]


def test():
    s = Solution()

def main():
    print("start main")
    test()

if __name__ == "__main__":
    main()
